/* eslint-disable no-new-object */
/* eslint-disable no-undef */
/* eslint-disable no-proto */
/* eslint-disable new-cap */
/* eslint-disable no-var */
/* eslint-disable no-unused-vars */
/* eslint-disable no-extend-native */
// https://leetcode-cn.com/circle/discuss/SVKmhR/
// 一、算法类
// 1. 快速排序、冒泡、选择排序

// 2. URL拆解问题
// 2.1
/**
 * --- 题目描述 ---
 * 实现一个函数，可以对 url 中的 query 部分进行拆解，返回一个 object = {key: value} 形式
 *
 * --- 实例 ---
 * 输入：https://example.com?a=xx&b=xxx&c=1
 * 输出: {a: xx, b: xx, c=1}
 */

function getURLObject (url = 'https://example.com?a=xx&b=xx%x&c=1#has') {
  const urls = url.split(/[?&#]/).slice(1) // [?&]: 匹配方括号中 "?" 、 "&" 或 "#" 符号. 并将其转化为数组后截取数组的1到数组最后一个
  const result = {}
  urls.forEach(item => {
    const [key, value] = item.split('=') // 数组解构出key和value值
    result[key] = decodeURIComponent(value || '') // 对url中value的值进行解码， decodeURIComponent只在浏览器平台有用
  })
  return result
}

// 2.2
/**
 * --- 题目描述 ---
 * 实现一个 parseParem 函数，将 url 转化为指定结果
 *
 * --- 实例 ---
 * 输入：url = 'http://www.domain.com/?user=anonymous&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled'
 * 输出: {
          user:'anonymous',
          id:[123,456],// 重复出现的 key 要组装成数组，能被转成数字的就转成数字类型
          city:'北京',// 中文需解码
          enabled: true // 未指定值的 key 与约定为 true
        }
 */

function parseParams (url = 'http://www.domain.com/?user=anonymous&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled') {
  const urls = url.split(/[?&#]/).slice(1)
  const result = {}
  urls.forEach(item => {
    const [key, value] = item.split('=')
    if (value === undefined) {
      result[key] = true
    } else {
      if (key in result) { // 判断key在result中是否存在
        Array.isArray(result[key]) ? result[key].push(value) : result[key] = [result[key]].concat(decodeURIComponent(value))
      } else {
        result[key] = decodeURIComponent(value)
      }
    }
  })
  return result
}

// 3. 将 HTTP header 转化为js对象
/**
 * --- 题目描述 ---
 * 实现一个方法，把 HTTP 文本形式(字符串)的 header 转换成 JS 对象。
 *
 * --- 测试用例 ---
 * 输入：
 * `Accept-Ranges: bytes
 *  Cache-Control: max-age=6000, public
 *  Connection: keep-alive
 *  Content-Type: application/javascript
 * `
 * 输出：
 * {
 *   "Accept-Ranges": "bytes",
 *   "Cache-Control": "max-age=6000, public",
 *   Connection: "keep-alive",
 *   "Content-Type": "application/javascript"
 * }
 */

function getHttpHeaders (headers) {
  const request = new XMLHttpRequest()
  request.open('GET', 'example.txt', true)
  request.send()
  const headerObj = {}
  request.onreadystatechange = function () {
    if (this.readyState === this.HEADERS_RECEIVED) {
      // get the raw header string
      const headers = request.getAllResponseHeaders()
      const array = headers.split(/[\n\r]+/)
      array.forEach(item => {
        const [key, value] = item.split(': ')
        headerObj[key] = value
      })
    }
  }
  // const headerObj = {}
  // const array = headers.split(/[\n\r]+/)
  // array.forEach(item=>{
  //   const [key, value] = item.split(': ')
  //   headerObj[key] = value
  // })
  return headerObj
}
// getHttpHeaders(headers)

// 4. 将数组转化为树形结构
// const groups = require('./group_data')
function buildGroupsTree (groups) {
  const roots = []; const leafs = []
  groups.forEach(group => {
    group.sub = [] // 为数组每个元素增加 sub 属性
    !group.up_id ? roots.push(group) : leafs.push(group) // 找出根节点和子节点，分别放入到响应的数组中
  })

  // 循环递归，将相应的子节点放入到父节点中
  function loop (roots = [], leafs = [], level = 1, parentNames = [], parentIds = []) {
    if (!leafs.length) return roots
    return roots.map(root => {
      const leafsTemp = []
      root.level = level
      root.parentNames = parentNames
      root.parentIds = parentIds
      leafs.forEach(leaf => {
        // 判断root的id是为leaf的父节点id， 是的话将其放入到相应的父节点中，否则放入空的字节点数组中
        if (root.id === leaf.up_id) {
          leaf.level = level + 1
          root.sub.push(leaf)
        } else {
          leafsTemp.push(leaf)
        }
      })
      leafs = leafsTemp
      loop(root.sub, leafsTemp, level + 1, [root.name, ...parentNames], [...parentIds, root.id])
      return root
    })
  }
  return loop(roots, leafs)
}
// const treeGroups = buildGroupsTree(groups)
// console.log(treeGroups[0].sub)

// 5. 数组扁平化 MDN(https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/flat)
// 方法一： flat([depth]) (depth: 制定要提取嵌套数组的结构深度，默认为1， Infinity 为∞即展开任意深度的嵌套数组)
const array1 = [1, 2, [3, 4]]
const array2 = [1, 2, [3, 4, [5, 6]]]
const array3 = [1, 2, [3, 4, [5, 6, [7, 8, [9, 10]]]]]
// console.log('flat(): ', array1.flat())
// console.log('flat(2): ', array2.flat(2))
// console.log('flat(Infinity): ', array3.flat(Infinity))

// 方法二： 展开一层（reducer / concat）
// console.log('flat(): ', array1.flat())
// array.reduce(callbackFn, initialValue)
// initialValue: 作为第一次调用callback函数时参数，如果有， curVal则为array[0]，否则curVal则为array[1]
// console.log('flat()1:', array1.reduce((preVal,curVal)=> preVal.concat(curVal), []) )
// console.log('flat()2:', [].concat(...array1))

// 方法三：循环递归
// 使用 reduce + concat 和递归展开无限多层嵌套的数组
function flatDeep (arr = [], dep = 1) {
  return dep > 0
    ? arr.reduce((acc, val) => acc.concat(Array.isArray(val) ? flatDeep(val, dep - 1) : val), [])
    : arr.slice()
}
// console.time('flatDeep') // 6.7ms -> 7.5ms
// console.log('flatDeep 1: ', flatDeep(array1))
// console.log('flatDeep 2: ', flatDeep(array2, 2))
// console.log('flatDeep Infinity: ', flatDeep(array3, Infinity))
// console.timeEnd('flatDeep')

// forEach 遍历数组会自动跳过空元素
const eachFlat = (arr = [], dep = 1) => {
  const result = [] // 存储递归结果
  // 开始递归
  function flat (arr, dep) {
    // forEach 会自动去除数组空位
    arr.forEach((item) => {
      // 控制递归深度
      if (Array.isArray(item) && dep > 0) {
        // 递归数组
        flat(item, dep - 1)
      } else {
        // 缓存元素
        result.push(item)
      }
    })
  }
  flat(arr, dep)
  return result
}
// console.time('eachFlat') // 0.36ms
// console.log('eachFlat 1: ', eachFlat(array1))
// console.log('eachFlat 2: ', eachFlat(array2, 2))
// console.log('eachFlat Infinity: ', eachFlat(array3, Infinity))
// console.timeEnd('eachFlat')

// 方法四： 无递归数组扁平化 -> 堆栈stack
// 注意：深度的控制比较低效，因为需要检查每个值的深度
// 也可能在 shift / unshift 上进行 w/o 反转， 但是末端的数组 OPs 更快
function flatten (input) {
  const stack = [...input]
  const result = []
  while (stack.length) {
    // 使用 pop 从 stack 中取出并移除值
    const next = stack.pop()
    if (Array.isArray(next)) {
      // 使用 push 送回内层数组中的元素，不会改动原始输入
      stack.push(...next)
    } else {
      result.push(next)
    }
  }
  // 反转恢复原始数组的顺序
  return result.reverse()
}

// console.time('flatten') // 6.89ms -> 12.464ms
// console.log('flatten 1: ', flatten(array1))
// console.log('flatten 2: ', flatten(array2))
// console.log('flatten Infinity: ', flatten(array3))
// console.timeEnd('flatten')

// 方法五：生成器 Generator
function * generatorFlatten (array) {
  for (const item of array) {
    if (Array.isArray(item)) {
      yield * generatorFlatten(item)
    } else {
      yield item
    }
  }
}
// console.time('generatorFlatten') // 6.77ms -> 7.43ms
// console.log('generatorFlatten 1: ', [...generatorFlatten(array1)])
// console.log('generatorFlatten 2: ', [...generatorFlatten(array2)])
// console.log('generatorFlatten Infinity: ', [...generatorFlatten(array3)])
// console.timeEnd('generatorFlatten')

// 6. 模拟 lodash 中的 get 方法
/**
 * --- 题目描述 ---
 * 模拟 lodash 中的 _.get() 函数。
 *
 * --- 测试用例 ---
 *
 * 输入：
 * const data = {a: {b: ['1','2', {c: 'abc'}]}}
 * _get(data, 'a.b[2].c')
 * 输出：'abc'
 */
function _get (object, path, defaultValue) {
  // 将数组格式路径转化成dot格式，再拆分成key数组
  // a[0].b => a.0.b => [a,0,b]
  const paths = path.replace(/\[(\d+)\]/g, '.$1').split('.')
  let result = object
  for (const p of paths) {
    result = Object(result)[p] // null 与 undefined 取属性会报错，用 Object 包装一下
  }
  return result || defaultValue
}
// const data = {a: {b: ['1','2', {c: 'abc'}]}}
// console.log('get:', _get(data, 'a.b[2].c'))

// 二、原理类
// 1. 深拷贝
// const clone = require('./deepClone')
// const map = new Map()
// map.set('name', 'husky')
// map.set('age', '26')
// const set = new Set()
// set.add('set1')
// set.add('set2')
// const object = {
//   str: 'str',
//   num: 1,
//   bool: false,
//   undefined: undefined,
//   null: null, // typeof 为 'object',
//   arr: [1, 2, 3, 4],
//   obj: { f: { f: { f: { f: { f: { f: 'f' } } } } } },
//   map,
//   set,
//   symbol: Symbol(10),
//   date: new Date(),
//   reg: /^\d+$/,
//   error: new Error('this is error'),
//   func1: () => console.log('func1'),
//   func2: function (a = 1, b = 2) {
//     return a + b
//   }

// }
// object.target = object // 循环引用 -> 由于递归进入死循环引导致栈内存溢出
// const newObj = clone(object)
// console.log({ newObj, object })

// 2. 浅拷贝
const init = {
  a: 1,
  b: 2,
  c: false
}
const obj1 = { ...init, a: null }
const obj2 = Object.assign(init, { b: null })
// console.log({ obj1, obj2 })

// 3. 手写bind函数
// https://github.com/sisterAn/JavaScript-Algorithms
// function.bind(thisArg[, arg1[, arg2[, ...]]])
// 1>、thisArg 为 new 运算符构造绑定函数，则忽略该值
// 2>、thisArg 在 setTimeout 中创建一个函数时，作为 thisArg 传递的任何原始值都将转化为object
// 3>、thisArg 为 null 或 undefined, 或参数列表为空，执行作用域的 this 将被视为新函数的 thisArg
// 4>、arg1, arg2...: 当目标函数被调用时，被预置入绑定函数的参数列表中的参数
// 5>、返回一个原函数的拷贝，并拥有指定的 this 值和初始参数
// 6>、特点：可以指定this、返回函数、传入参数、柯里化

Function.prototype.bind1 = function (context) {
  // 当调用bind的不是函数时，抛出异常
  if (typeof this !== 'function') {
    return new Error('Function.prototype.bind - what is trying to be bound is not callable')
  }
  var self = this // 将this指向调用者

  // 获取绑定函数传入的参数, arguments 的第一个参数为this，所以截取this后的参数
  var args = Array.prototype.slice.call(arguments, 1)

  // 创建空对象
  // 绑定函数传入new操作符创建对象时，this值被忽略，同时调用时的参数被提供给模拟函数
  var fNOP = function () {} // 待理解，原型继承

  var funBound = function () { // 返回一个函数
    // 柯里化，此时的 arguments 是指 bind 返回的函数传入的参数
    var bindArgs = Array.prototype.slice.call(arguments)

    // 使用 apply 指定 this
    return self.apply(
      this instanceof fNOP ? this : context,
      args.concat(bindArgs)
    )
  }
  // 将空对象的原型指向绑定函数的原型
  fNOP.prototype = this.prototype
  // 空对象的实例赋值给 funBound.prototype
  funBound.prototype = new fNOP()
  return funBound
}

// 测试用例
var value = 2
var foo = {
  value: 1
}
function bar (name, age) {
  this.habit = 'working'
  const obj = {
    value: this.value,
    name,
    age
  }
  console.log(this.value, obj, this.habit)
  // return this.value
  // return {
  //   value: this.value,
  //   name,
  //   age
  // }
}
// bar.prototype.friend = 'Liang'
// var bindFun = bar.bind1(foo, 'Husky')
// var newObj = new bindFun(26)
// console.log('habit:', newObj.habit)
// console.log('friend:', newObj.friend)

// 4. 手写new
// 定义：new 运算符创建一个用户定义的对象类型的实例或具有构造函数的内容值对象的实例
// 语法：new constructor[([arguments])]
// constructor: 一个指定对象实例的类型的类或函数
// arguments: 一个用于被 constructor 调用的参数列表
// new 关键字会进行如下操作
// 1. 创建一个空的简单JavaScript对象（即{}）
// 2. 为1新创建的对象添加属性__proto__， 将该属性链接至构造函数的原型对象
// 3. 将1创建的对象作为this的上下文
// 4. 如果该函数没有返回对象，则返回this
// 模拟实现（当代码 new Foo(...) 执行时，会发生以下的事情： ）
// 1. 一个继承自 Foo.prototype 的新对象被创建
// 2. 使用指定的参数调用构造函数 Foo，并将this绑定到新创建的对象。new Foo 等同于 new Foo(), 也就是没有指定参数列表， Foo不带任何参数调用的情况
// 3. 由构造函数返回的对象就是 new 表达式的结果，如果构造函数没有显式返回一个对象，则使用1创建的对象
function create () {
  // 创建一个空的对象
  var obj = new Object()
  // 获取构造函数，arguments中去除第一个参数
  var Con = [].shift.call(arguments)
  // 链接到原型， obj 可以访问到构造函数原型中的属性
  obj.__proto__ = Con.prototype
  // 绑定this 实现继承，obj 可以访问到构造函数中的属性
  var ret = Con.apply(obj, arguments)
  // 优先返回构造函数返回的对象
  return ret instanceof Object ? ret : obj
}

// function Car (name) {
//   this.name = name
// }
// Car.prototype.start = function () {
//   console.log(this.name + 'Start!')
// }
// const car = create(Car, '尉来')
// console.log(car.name)
// car.start()

// 5. 手动实现 instanceof
// instanceof 运算符用于检测构造函数的prototype属性（constructor.prototype）是否出现在某个实例对象(object)的原型链上
function instanceof1 (a, b) {
  var prototypeA = Object.getPrototypeOf(a) // 返回指定对象的原型
  var prototypeB = b.prototype
  while (prototypeA) {
    if (prototypeA === prototypeB) return true
    prototypeA = Object.getPrototypeOf(prototypeA)
  }
  return false
}

function instanceof2 (left, right) {
  if (typeof left !== 'object' || right == null) return false
  var rightPrototype = right.prototype
  left = left.__proto__
  while (true) {
    if (left === null) return false
    if (left === rightPrototype) return true
    left = left.__proto__
  }
}
// const a = []
// const b = {}
// const c = ''
// function Car () {}
// const car = new Car()
// console.log('[] instanceof Array', instanceof1(a, Array))
// console.log('[] instanceof Array', instanceof2(a, Array))
// console.log('[] instanceof Object', instanceof1(a, Object))
// console.log('[] instanceof Object', instanceof2(b, Object))
// console.log('"" instanceof String', instanceof1(c, String))
// console.log('"" instanceof String', instanceof2(c, String))
// console.log('car instanceof Car', instanceof1(car, Car))
// console.log('car instanceof Car', instanceof2(car, Car))

// 6. 手写节流函数(throttle)
// 适用于函数被频繁调用的场景：window.onresize()、mousemove、上传进度等
// 方案一：用时间戳来判断是否已经到执行的时间，记录上次执行的时间戳，然后每次触发事件执行回调，
// 回调中判断当前时间戳距离上次执行时间戳的间隔是否已经达到时间差，如果是执行，并更新上次执行的时间戳，如此循环
/**
 * @param {*} fn // 需要执行的函数
 * @param {*} wait // 时间间隔
 */
const throttle = (fn, wait = 50) => {
  // 上一次执行 fn 的时间
  let previous = 0
  // 将 throttle 处理结果当作函数返回
  return function (...args) {
    // 获取当前时间，转换成时间戳，单位毫秒
    const now = +new Date()
    // 将当前时间和上一次执行函数的时间进行对比
    // 大于等待时间就把 previous 设置为当前时间并执行函数 fn
    if (now - previous > wait) {
      previous = now
      fn.apply(this, args)
    }
  }
}

// 方案二：使用定时器，如果存在定时器，则回调不执行方法，知道定时器触发，函数被清除，然后重新设置定时器
const throttle1 = (fn, delay) => {
  let timer = null
  return function () {
    if (timer) return
    timer = setTimeout(() => {
      fn.apply(this.arguments)
      timer = null
    }, delay)
  }
}
// 执行 throttle 函数返回新函数
const betterFn = throttle1(() => console.log('fn 函数执行了'), 500)
// 每 10 毫秒执行一次 betterFn 函数，但是只有时间差大于 1000 时才会执行 fn
setInterval(betterFn, 100)

/**
 * @param {*} func
 * @param {*} wait
 * @param {*} options // {leading = false, trailing = false}
 * leading: 配置是否需要响应事件刚开始的那次回调，false时忽略
 * trailing:配置是否需要响应事件结束后的那次回调，false时忽略
 */
const throttle2 = (func, wait, options) => {
  let timeout, context, args, result
  // 上一次执行回调的时间戳
  let previous = 0

  // 无参数传入时，初始化 options 为空对象
  if (!options) options = {}

  const later = function () {
    // 当设置 {leading: false} 时
    // 每次触发回调函数后设置 previous 为 0
    // 不然为当前时间
    previous = options.leading === false ? 0 : +new Date()

    // 防止内存泄漏，设置为 null便于后面根据 !timeout 设置新的 timeout
    timeout = null

    // 执行函数
    result = func.apply(context, args)
    if (!timeout) context = args = null
  }

  // 每次触发事件回调都执行这个函数
  // 函数内判断是否执行了 func
  // func 才是我们业务层代码想要执行的函数
  const throttle = function () {
    // 记录当前的时间
    const now = +new Date()

    // 第一次执行时（此时 previous 为 0， 之后为上次时间戳）
    // 并设置了 {leading: false}（表示第一次回调不执行）
    // 此时设置 previous 为当前值，表示刚执行过，本次就不执行了
    if (!previous && options.leading === false) previous = now

    // 距离下次触发 func 还需要等待的时间
    const remaining = wait - (now - previous)
    context = this
    args = arguments

    // 要么是到了间隔时间了，随即触发方法(remaining <= 0)
    // 要么是没有传入 {leading: false}，且第一次触发回调，即立即触发
    // 此时 previous 为 0， wait - (now - previous) 也满足 <= 0
    // 之后便会把 previous 设置为 now
    if (remaining <= 0 || remaining > wait) {
      if (timeout) {
        clearTimeout(timeout)
        // clearTimeout(timeout) 并不会把 timeout 设置为 null
        // 手动设置，便于后续判断
        timeout = null
      }
      // 设置 previous 为当前时间
      previous = now
      // 执行 func 函数
      result = func.apply(context, args)
      if (!timeout) context = args = null
    } else if (!timeout && options.trailing !== false) {
      // 最后一次需要触发的情况
      // 如果已经存在一个定时器，则不会进入该判断
      // 如果 {trailing: false}, 即最后一次不需要触发了，也不会进入该判断
      // 间隔 remaining millisecond 后触发 later 方法
      timeout = setTimeout(later, remaining)
    }
    return result
  }

  // 手动取消
  throttle.cancel = function () {
    clearTimeout(timeout)
    previous = 0
    context = args = timeout = null
  }

  // 执行 throttle 函数并返回
  return throttle
}

// 7. 手写防抖函数(debounce)
// 原理：利用定时器，函数第一次执行时设定一个定时器，之后调用时发现已经设定过定时器就清空之前的定时器
// 并重新设定一个新的定时器，如果存在没有被清空的定时器，当定时器结束后触发函数执行
// 实现1
/**
 * @param {*} fn 需要防抖处理的函数
 * @param {*} wait 时间间隔
 */
const debounce = (fn, wait = 50) => {
  // 通过闭包缓存一个定时器 id
  let timer = null
  // 将 debounce 处理结果当作函数返回
  // 触发事件回调时执行这个返回函数
  return function (...args) {
    // 如果已经设定过定时器就清空上一次的定时器
    if (timer) clearTimeout(timer)

    // 开始设定一个新的定时器，定时器结束后执行传入的函数 fn
    timer = setTimeout(() => {
      fn.apply(this, ...args)
    }, wait)
  }
}

// 实现2
/**
 * @param {*} fn 需要防抖处理的函数
 * @param {*} wait 时间间隔
 * @param {*} immediate 表示第一次是否立即执行
 */
// const debounce1 = (fn, wait, immediate) => {
//   let timeout, // 表示定时器
//     result // 表示 fn 执行返回值

//   // 定时器计时结束后
//   // 1. 清空计时器，使之不影响下次连续事件的触发
//   // 2. 触发执行 func
//   const later = function (context, args) {
//     timeout = null
//     // if(args)判断时为了过滤立即触发的
//     // 关联在于 delay 和 restArguments
//     if (args) result = fn.apply(context, args)
//   }

//   // 将debounce 处理结果当作函数返回
//   const debounce = restArguments(function (args) {
//     if (timeout) clearTimeout(timeout)
//     if (immediate) {
//       // 第一次触发后会设置timeout
//       // 根据 timeout 是否为空可以判断是否首次触发
//       const now = !timeout
//       timeout = setTimeout(later, wait)
//       if (now) result = fn.apply(this, args)
//     } else {
//       // 设置定时器
//       timeout = delay(later, wait, this, args)
//     }
//     return result
//   })

//   // 手动取消
//   debounce.cancel = function () {
//     clearTimeout(timeout)
//     timeout = null
//   }

//   return debounce
// }

// 三、应用类
